/*
题目: 统计优美子数组
给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中 「优美子数组」 的数目。

https://leetcode.cn/problems/count-number-of-nice-subarrays
 */
public class NumberOfBeautySubarrays {
    public int numberOfSubarrays(int[] nums, int k) {
        // 此题可以等效为 : 奇数为1, 偶数为0, 子区间和为k的种类数
        // 存在 一条 Key 个奇数的路径 Value 个
        Map<Integer, Integer> map = new HashMap<> ();
        map.put(0, 1);
        int odd = 0, n = nums.length;;

        int src = 0;
        for (int i = 0; i < n; i ++) {
            odd += (nums[i] & 1) == 1 ? 1 : 0;

            src += map.getOrDefault(odd - k, 0);
            map.put(odd, map.getOrDefault(odd, 0) + 1);
        }

        return src ;
    }
}
